home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 1 / LSD Compendium Deluxe 1.iso / a / programming / assembly / clip.lha / polyclip2.code / text0000.txt < prev   
Encoding:
Text File  |  1989-10-24  |  5.6 KB  |  238 lines
  1. The following is a package which maintains polygons and includes a
  2. routine to clip polygons to a rectangle.  It is written in an
  3. object-oriented style.  It works quite well.  The first file is an
  4. example of how you'd put it to use, the second is a simple definition of
  5. a viewport (clipping rectangle), the third is the polygon header file to
  6. be included by other modules, and the fourth is the polygon code file.
  7.  
  8. Curt McDowell
  9. Carnegie Mellon University
  10.  
  11. --- FILE EXAMPLE.C ---
  12. #include <stdio.h>
  13. #include <polygon.h>
  14. #include <viewport.h>
  15.  
  16. main(argc, argv)
  17. char **argv;
  18. {
  19.     struct polygon *p;
  20.     struct viewport v;
  21.  
  22.     p = polygon_New();
  23.  
  24.     polygon_Insert(p, 10, 100);
  25.     polygon_Insert(p, ..., ...);
  26.     ... etc ...;
  27.  
  28.     v.left = 1;
  29.     v.top = ...;
  30.     v.width = ...;
  31.     v.height = ...;
  32.  
  33.     polygon_Clip(p, &v);
  34.  
  35.     printf("Clipped polygon:\n");
  36.  
  37.     for (i = 0; i < p->n; i++)
  38.         printf("(%d,%d)\n", p->x[i], p->y[i]);
  39. }
  40.  
  41. --- FILE VIEWPORT.H ---
  42. struct viewport {
  43.     int left, top;
  44.     int width, height;
  45. };
  46. --- FILE POLYGON.H ---
  47. /*
  48.  * Polygon data structure
  49.  */
  50.  
  51. struct polygon {
  52.     short n, alloc;
  53.     short *x, *y;
  54. };
  55.  
  56. #define polygon_Clear(p) ((p)->n = 0)
  57.  
  58. extern struct polygon *polygon_New();
  59. extern void polygon_Insert();
  60. extern void polygon_Destroy();
  61. extern void polygon_Clip();
  62. --- FILE POLYGON.C ---
  63. /*
  64.  * Polygon object
  65.  * by Curt McDowell, CMU Information Technology Center
  66.  *
  67.  * This code comes under the IBM Copyright of the Andrew Toolkit,
  68.  * which is to say, you can do anything but sell it.
  69.  */
  70.  
  71. #include <polygon.h>
  72. #include <viewport.h>
  73.  
  74. char *malloc(), *realloc();
  75.  
  76. /* Similar triangle macro:
  77.  * Given three coordinates along axis 1 and two
  78.  * along axis 2, finds the third on axis 2 which
  79.  * falls between the two on axis 1. */
  80.  
  81. #define ClipCase(left, middle, right, start, end) \
  82.      (((start) * ((right) - (middle)) + \
  83.        (end) * ((middle) - (left))) / ((right) - (left)))
  84.  
  85. /* Polygon manipulation:
  86.  * Dynamically allocated polygon structure
  87.  * Use this to create and destroy polygons to be
  88.  * passed to the clipping and filling routines. */
  89.  
  90. struct polygon *polygon_New()
  91. {
  92.     struct polygon *p;
  93.     p = (struct polygon *) malloc(sizeof (struct polygon));
  94.     p->alloc = 8;
  95.     p->x = (short *) malloc(p->alloc * sizeof (short));
  96.     p->y = (short *) malloc(p->alloc * sizeof (short));
  97.     p->n = 0;
  98.     return p;
  99. }
  100.  
  101. void polygon_Insert(p, x, y)
  102. struct polygon *p;
  103. short x, y;
  104. {
  105.     if (p->n == p->alloc) {
  106.         p->alloc *= 2;
  107.         p->x = (short *) realloc(p->x, p->alloc * sizeof (short));
  108.         p->y = (short *) realloc(p->y, p->alloc * sizeof (short));
  109.     }
  110.     p->x[p->n] = x;
  111.     p->y[p->n] = y;
  112.     p->n++;
  113. }
  114.  
  115. void polygon_Destroy(p)
  116. struct polygon *p;
  117. {
  118.     free(p->x);
  119.     free(p->y);
  120.     free(p);
  121. }
  122.  
  123. /*
  124.  * Clip Polygon associated code
  125.  */
  126.  
  127. #define edge_LEFT       0
  128. #define edge_RIGHT      1
  129. #define edge_ABOVE      2
  130. #define edge_BELOW      3
  131.  
  132. static short Inside(x, y, v, which)
  133. short x, y;
  134. struct viewport *v;
  135. short which;
  136. {
  137.     switch (which) {
  138.         case edge_ABOVE:
  139.             return (y >= v->top);
  140.         case edge_BELOW:
  141.             return (y < v->top + v->height);
  142.         case edge_LEFT:
  143.             return (x >= v->left);
  144.         case edge_RIGHT:
  145.             return (x < v->left + v->width);
  146.     }
  147. }
  148.  
  149. static void Intersect(px, py, fx, fy, tx, ty, v, which)
  150. short *px, *py;
  151. short fx, fy, tx, ty;
  152. struct viewport *v;
  153. short which;
  154. {
  155.     switch (which) {
  156.         case edge_ABOVE:
  157.             *py = v->top;
  158.             *px = ClipCase(fy, *py, ty, fx, tx);
  159.             break;
  160.         case edge_BELOW:
  161.             *py = v->top + v->height - 1;
  162.             *px = ClipCase(fy, *py, ty, fx, tx);
  163.             break;
  164.         case edge_LEFT:
  165.             *px = v->left;
  166.             *py = ClipCase(fx, *px, tx, fy, ty);
  167.             break;
  168.         case edge_RIGHT:
  169.             *px = v->left + v->width - 1;
  170.             *py = ClipCase(fx, *px, tx, fy, ty);
  171.             break;
  172.     }
  173. }
  174.  
  175. static void ClipEdge(in, out, v, which)
  176. struct polygon *in, *out;
  177. struct viewport *v;
  178. short which;
  179. {
  180.     short i, ix, iy;
  181.  
  182.     i = 0;
  183.     out->n = 0;
  184.  
  185.     do {
  186.         /* case I loop as long as inside */
  187.         while (i < in->n && Inside(in->x[i], in->y[i], v, which)) {
  188.             polygon_Insert(out, in->x[i], in->y[i]);
  189.             i++;
  190.         }
  191.         if (i < in->n) {
  192.             /* case II unless first point is outside */
  193.             if (i > 0) {
  194.                 Intersect(&ix, &iy, in->x[i - 1], in->y[i - 1],
  195.                                     in->x[i], in->y[i], v, which);
  196.                 polygon_Insert(out, ix, iy);
  197.             }
  198.             /* case III loop as long as outside */
  199.             while (i < in->n && ! Inside(in->x[i], in->y[i], v, which))
  200.                 i++;
  201.             /* case IV outside to inside */
  202.             if (i < in->n) {
  203.                 Intersect(&ix, &iy, in->x[i - 1], in->y[i - 1],
  204.                                     in->x[i], in->y[i], v, which);
  205.                 polygon_Insert(out, ix, iy);
  206.             }
  207.         }
  208.     } while (i < in->n);
  209.  
  210.     /* Now check if there's a crossing between the last & first points */
  211.  
  212.     if (Inside(in->x[in->n - 1], in->y[in->n - 1], v, which) ^
  213.         Inside(in->x[0], in->y[0], v, which)) {
  214.         Intersect(&ix, &iy, in->x[in->n - 1], in->y[in->n - 1],
  215.                             in->x[0], in->y[0], v, which);
  216.         polygon_Insert(out, ix, iy);
  217.     }
  218. }
  219.  
  220. void polygon_Clip(p, v)
  221. struct polygon *p;
  222. struct viewport *v;
  223. {
  224.     static struct polygon *t = 0;  /* temporary polygon, stays around */
  225.  
  226.     if (t == 0)
  227.         t = polygon_New();
  228.     else
  229.         t->n = 0;
  230.  
  231.     ClipEdge(p, t, v, edge_ABOVE);
  232.     ClipEdge(t, p, v, edge_BELOW);
  233.     ClipEdge(p, t, v, edge_LEFT);
  234.     ClipEdge(t, p, v, edge_RIGHT);
  235. }
  236.  
  237.  
  238.